{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #将字符串翻转到单调递增"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minFlipsMonoIncr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将字符串翻转到单调递增"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果一个由&nbsp;<code>&#39;0&#39;</code> 和 <code>&#39;1&#39;</code>&nbsp;组成的字符串，是以一些 <code>&#39;0&#39;</code>（可能没有 <code>&#39;0&#39;</code>）后面跟着一些 <code>&#39;1&#39;</code>（也可能没有 <code>&#39;1&#39;</code>）的形式组成的，那么该字符串是&nbsp;<strong>单调递增&nbsp;</strong>的。</p>\n",
    "\n",
    "<p>我们给出一个由字符 <code>&#39;0&#39;</code> 和 <code>&#39;1&#39;</code>&nbsp;组成的字符串 <font color=\"#c7254e\" face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"caret-color: rgb(199, 37, 78); font-size: 12.600000381469727px; background-color: rgb(249, 242, 244);\">s</span></font>，我们可以将任何&nbsp;<code>&#39;0&#39;</code> 翻转为&nbsp;<code>&#39;1&#39;</code>&nbsp;或者将&nbsp;<code>&#39;1&#39;</code>&nbsp;翻转为&nbsp;<code>&#39;0&#39;</code>。</p>\n",
    "\n",
    "<p>返回使 <font color=\"#c7254e\" face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"caret-color: rgb(199, 37, 78); font-size: 12.600000381469727px; background-color: rgb(249, 242, 244);\">s</span></font>&nbsp;<strong>单调递增&nbsp;</strong>的最小翻转次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s =<strong> </strong>&quot;00110&quot;\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>我们翻转最后一位得到 00111.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s =<strong> </strong>&quot;010110&quot;\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>我们翻转得到 011111，或者是 000111。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s =<strong> </strong>&quot;00011000&quot;\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>我们翻转得到 00000000。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 20000</code></li>\n",
    "\t<li><font color=\"#c7254e\" face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"caret-color: rgb(199, 37, 78); font-size: 12.600000381469727px; background-color: rgb(249, 242, 244);\">s</span></font> 中只包含字符&nbsp;<code>&#39;0&#39;</code>&nbsp;和&nbsp;<code>&#39;1&#39;</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 926&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/flip-string-to-monotone-increasing/\">https://leetcode-cn.com/problems/flip-string-to-monotone-increasing/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cyJERH](https://leetcode.cn/problems/cyJERH/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cyJERH](https://leetcode.cn/problems/cyJERH/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"00110\"', '\"010110\"', '\"00011000\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        res = 0\n",
    "        zero,one = 0,0\n",
    "        for i in s:\n",
    "            x = int(i)\n",
    "            if x:\n",
    "                one += 1\n",
    "            elif one>0:\n",
    "                zero+=1\n",
    "                if zero>=one:\n",
    "                    res += zero\n",
    "                    zero,one = 0,0\n",
    "        res += zero\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        zero, one = 0, 0\n",
    "        for i in range(len(s)):\n",
    "            flag = int(s[i])\n",
    "            zero, one =  zero+flag, min(zero, one) + 1 - flag\n",
    "        return min(zero, one)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        a = b = 0\n",
    "        for c in s:\n",
    "            a, b = a + int(c), min(a, b) + 1 - int(c)\n",
    "        return min(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        ans=pre=0\n",
    "        for i in s:\n",
    "            if i=='0':\n",
    "                ans=min(ans+1,pre)\n",
    "            else:\n",
    "                pre+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        flit_to_zero,flip_to_one = 0, s.count(\"0\")\n",
    "\n",
    "        minflips = flip_to_one\n",
    "        for ch in s:\n",
    "            if ch==\"0\":\n",
    "                flip_to_one -= 1\n",
    "            else:\n",
    "                flit_to_zero += 1\n",
    "\n",
    "            minflips = min(minflips,flip_to_one+flit_to_zero)\n",
    "        return minflips\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        ans = cnt0 = s.count('0')\n",
    "        cnt1 = 0\n",
    "        for c in s:\n",
    "            if c == '0':\n",
    "                cnt0 -= 1\n",
    "            else:\n",
    "                cnt1 += 1\n",
    "            ans = min(ans, cnt0 + cnt1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [0, 1] if s[0] == '0' else [1, 0]\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == '0':\n",
    "                dp = [dp[0], min(dp) + 1]\n",
    "            else:\n",
    "                dp = [dp[0] + 1, min(dp)]\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        zeros, ones = 0, 0\n",
    "        n = len(s)\n",
    "        for c in s:\n",
    "            if(c == '0'):\n",
    "                zeros += 1\n",
    "            else:\n",
    "                ones += 1\n",
    "        pre_zeros = 0\n",
    "        pre_ones = 0\n",
    "        result = n\n",
    "        result = min(result,n-ones,n-zeros)\n",
    "        for i,c in enumerate(s):\n",
    "            if(c == '0'):\n",
    "                pre_zeros += 1\n",
    "            else:\n",
    "                pre_ones += 1\n",
    "            #前0后1\n",
    "            result = min(result, i+1-pre_zeros + n-i-1-(ones-pre_ones))\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "\n",
    "        dp_0,dp_1=0,0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if (s[i]=='0'):\n",
    "                dp_1 = min(dp_0,dp_1)+1\n",
    "            else:\n",
    "                dp_1=min(dp_0, dp_1)\n",
    "                dp_0 += 1\n",
    "\n",
    "        return min(dp_0,dp_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        a,b=0,0\n",
    "        for i in range(n):\n",
    "            a,b=a+(1 if s[i]=='1' else 0), min(a,b)+(1 if s[i]=='0' else 0)\n",
    "        return min(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        # 状态转移需要考虑两种情况时，采用二维动态规划\n",
    "        # 分解子问题：\n",
    "        # 当[0,i-1]单调时，[0,i]单调所需的翻转次数取决与[0,i-1]的翻转次数和i处0/1的选择\n",
    "        # 记dp[i][0] dp[i][1] 分别为s[i]=='0'/'1'时使得数组单调所需的最小翻转次数\n",
    "        # dp[0][0] dp[0][1]只取决于s[0]的值\n",
    "        # 动态转移方程：(记函数b2n为bool2num)\n",
    "        # dp[i][0] = dp[i-1][0] + b2n(s[i]=='1')\n",
    "        # dp[i][1] = min(dp[i-1][0],dp[i-1][1]) + b2n(s[i]=='0')\n",
    "\n",
    "        # 最终结果为min(dp[0][0],dp[0][1])\n",
    "        # 为减小空间复杂度，记dp[0][0],dp[0][1]为p,q\n",
    "\n",
    "        p = int(s[0]=='1')\n",
    "        q = int(s[0]=='0')\n",
    "\n",
    "        for i in range(1,len(s)):\n",
    "            new_p = p + int(s[i]=='1')\n",
    "            new_q = min(p,q) + int(s[i]=='0')\n",
    "\n",
    "            p = new_p\n",
    "            q = new_q\n",
    "        \n",
    "        return min(p,q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[0]*n\n",
    "        one=0\n",
    "        zero=0\n",
    "        change=0\n",
    "        for i in range(n):\n",
    "            if s[i]=='1':\n",
    "                one+=1\n",
    "            if one>0 and s[i]=='0':\n",
    "                change+=1\n",
    "            \n",
    "            if one>0 and change>one:\n",
    "                change=one\n",
    "\n",
    "            dp[i]=change\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0] * (n+1)\n",
    "        ones = 0\n",
    "        for i in range(1, n+1):\n",
    "            if s[i-1] == \"1\":\n",
    "                dp[i] = dp[i-1]\n",
    "                ones += 1\n",
    "            else:\n",
    "                dp[i] = min(dp[i-1]+1, ones)\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp=[0 for _ in range(len(s)-1)]\n",
    "        \n",
    "        #if s.find('0')==-1:\n",
    "        #    return 0\n",
    "        #ind1=s.find('1')\n",
    "        #if ind1==-1:\n",
    "        #    return 0\n",
    "        #else:\n",
    "        #    if s[ind1:].find('0')==-1:\n",
    "        #        return 0\n",
    "            \n",
    "        dp[0]=0\n",
    "        ones=1 if s[0]=='1' else 0\n",
    "        for i in range(1,len(s)-1):\n",
    "            if not ones:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=0\n",
    "                    ones+=1\n",
    "                else:\n",
    "                    dp[i]=0\n",
    "            else:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=dp[i-1]\n",
    "                    ones+=1\n",
    "                else:\n",
    "                    dp[i]=min(ones,dp[i-1]+1)\n",
    "        \n",
    "        return min(ones, dp[-1]+1) if s[-1] =='0' else dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ones, zeros = [0]*n, [0]*n\n",
    "        one = 0 \n",
    "        for i in range(n):\n",
    "            ones[i] = one\n",
    "            one+=s[i]==\"1\"\n",
    "        zero=0\n",
    "        for i in range(n-1, -1, -1):\n",
    "            zero += s[i] == '0'\n",
    "            zeros[i] = zero\n",
    "        return min(min(ones[i] + zeros[i] for i in range(n)), zero, one)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        # 前缀和\n",
    "        res = [int(x) for x in list(s)]\n",
    "        n, sum_one, front_cone = len(res),sum(res),0  #数组长度，1的个数，遇到1的个数\n",
    "        ans = min(sum_one, n - sum_one) # 所有1变成0 ，或所有0变成1\n",
    "\n",
    "        for i in range(n):\n",
    "            if res[i] == 1:\n",
    "                front_cone += 1 #计算1的个数\n",
    "            one2zero = front_cone # 路过1全变成0\n",
    "            zero2one = (n - i - 1) - (sum_one - front_cone) #后面的0全部变成1 ，即后面元素个数-后面1的个数\n",
    "\n",
    "            ans = min(ans, one2zero+zero2one)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp=[0 for _ in range(len(s)-1)]\n",
    "        \n",
    "        #if s.find('0')==-1:\n",
    "        #    return 0\n",
    "        #ind1=s.find('1')\n",
    "        #if ind1==-1:\n",
    "        #    return 0\n",
    "        #else:\n",
    "        #    if s[ind1:].find('0')==-1:\n",
    "        #        return 0\n",
    "            \n",
    "        dp[0]=0\n",
    "        ones=1 if s[0]=='1' else 0\n",
    "        for i in range(1,len(s)-1):\n",
    "            if not ones:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=0\n",
    "                    ones+=1\n",
    "                else:\n",
    "                    dp[i]=0\n",
    "            else:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=dp[i-1]\n",
    "                    ones+=1\n",
    "                else:\n",
    "                    dp[i]=min(ones,dp[i-1]+1)\n",
    "        \n",
    "        return min(ones, dp[-1]+1) if s[-1] =='0' else dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp=[0 for _ in range(len(s)-1)]\n",
    "        \n",
    "        #if s.find('0')==-1:\n",
    "        #    return 0\n",
    "        #ind1=s.find('1')\n",
    "        #if ind1==-1:\n",
    "        #    return 0\n",
    "        #else:\n",
    "        #    if s[ind1:].find('0')==-1:\n",
    "        #        return 0\n",
    "            \n",
    "        dp[0]=0\n",
    "        ones=1 if s[0]=='1' else 0\n",
    "        for i in range(1,len(s)-1):\n",
    "            if not ones:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=0\n",
    "                    ones+=1\n",
    "                else:\n",
    "                    dp[i]=0\n",
    "            else:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=dp[i-1]\n",
    "                    ones+=1\n",
    "                else:\n",
    "                    dp[i]=min(ones,dp[i-1]+1)\n",
    "        \n",
    "        return min(ones, dp[-1]+1) if s[-1] =='0' else dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        counter = 0\n",
    "        for c in s:\n",
    "            if c == '0': counter += 1\n",
    "        res = [counter]\n",
    "        for c in s:\n",
    "            counter = res[-1]\n",
    "            if c == '0': counter -= 1\n",
    "            else: counter += 1\n",
    "            res.append(counter)\n",
    "        return min(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp=[0 for _ in range(len(s))]\n",
    "        dp[0]=0\n",
    "        ones=1 if s[0]=='1' else 0\n",
    "        for i in range(1,len(s)):\n",
    "            if not ones:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=0\n",
    "                    ones+=1\n",
    "                else:\n",
    "                    dp[i]=0\n",
    "            else:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=dp[i-1]\n",
    "                    ones+=1\n",
    "                else:\n",
    "                    dp[i]=min(ones,dp[i-1]+1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp=[0 for _ in range(len(s)-1)]\n",
    "        \n",
    "        if s.find('0')==-1:\n",
    "            return 0\n",
    "        ind1=s.find('1')\n",
    "        if ind1==-1:\n",
    "            return 0\n",
    "        else:\n",
    "            if s[ind1:].find('0')==-1:\n",
    "                return 0\n",
    "            \n",
    "        dp[0]=0\n",
    "        ones=1 if s[0]=='1' else 0\n",
    "        for i in range(1,len(s)-1):\n",
    "            if not ones:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=0\n",
    "                    ones+=1\n",
    "                else:\n",
    "                    dp[i]=0\n",
    "            else:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=dp[i-1]\n",
    "                    ones+=1\n",
    "                else:\n",
    "                    dp[i]=min(ones,dp[i-1]+1)\n",
    "        \n",
    "        return min(ones, dp[-1]+1) if s[-1] =='0' else dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        postfix = [0] * (n + 1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            postfix[i] = postfix[i + 1] + 1 - int(s[i])\n",
    "        if postfix[0] in {0, n}:    return 0\n",
    "\n",
    "        pre, minCnt = 0, postfix[0]\n",
    "        for i in range(n):\n",
    "            if s[i] == \"1\":\n",
    "                pre += 1\n",
    "            minCnt = min(minCnt, pre + postfix[i+1])\n",
    "            if not minCnt:  return 0\n",
    "        return minCnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        method = 'mine'\n",
    "        if method == 'mine':\n",
    "            n = len(s)\n",
    "            dp1 = [0] * n #第i位翻转为0的最小翻转次数\n",
    "            dp2 = [0] * n #第i位翻转为1的最小翻转次数\n",
    "            if s[0] == '0':\n",
    "                dp1[0] = 0\n",
    "                dp2[0] = 1\n",
    "            else:\n",
    "                dp1[0] = 1\n",
    "                dp2[0] = 0\n",
    "            for i in range(1, n):\n",
    "                if s[i] == '0':\n",
    "                    dp1[i] = dp1[i - 1]\n",
    "                    dp2[i] = min(dp1[i - 1], dp2[i - 1]) + 1\n",
    "                else:\n",
    "                    dp1[i] = dp1[i - 1] + 1\n",
    "                    dp2[i] = min(dp1[i - 1], dp2[i - 1])\n",
    "            return min(dp1[-1], dp2[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        presum = [0 for _ in range(n+1)]\n",
    "        for i, c in enumerate(s):\n",
    "            presum[i + 1] = presum[i] + (c == '1')\n",
    "        res = n\n",
    "        for mid in range(n + 1):\n",
    "            L1 = presum[mid]\n",
    "            r0 = (n - mid) - (presum[n] - presum[mid])\n",
    "            res = min(res, L1 + r0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        presum = [0 for _ in range(n + 1)]\n",
    "        for i, c in enumerate(s):\n",
    "            presum[i + 1] = presum[i] + (c == '1')\n",
    "        \n",
    "        res = n\n",
    "        for mid in range(n + 1):    #左侧有mid个数字，mid属于右侧部分\n",
    "            L1 = presum[mid]\n",
    "            R0 = (n - mid) - (presum[n] - presum[mid])\n",
    "            res = min(res, L1 + R0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp=[0 for _ in range(len(s))]\n",
    "        ones=[0 for _ in range(len(s))]\n",
    "        dp[0]=0\n",
    "        ones[0]=1 if s[0]=='1' else 0\n",
    "        for i in range(1,len(s)):\n",
    "            if not ones[i-1]:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=0\n",
    "                    ones[i]=1\n",
    "                else:\n",
    "                    dp[i]=0\n",
    "                    ones[i]=0\n",
    "            else:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=dp[i-1]\n",
    "                    ones[i]=ones[i-1]+1\n",
    "                else:\n",
    "                    ones[i]=ones[i-1]\n",
    "                    dp[i]=min(ones[i],dp[i-1]+1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp=[0 for _ in range(len(s))]\n",
    "        ones=[0 for _ in range(len(s))]\n",
    "        dp[0]=0\n",
    "        ones[0]=1 if s[0]=='1' else 0\n",
    "        for i in range(1,len(s)):\n",
    "            if not ones[i-1]:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=0\n",
    "                    ones[i]=1\n",
    "                else:\n",
    "                    dp[i]=0\n",
    "                    ones[i]=0\n",
    "            else:\n",
    "                if s[i] == '1':\n",
    "                    dp[i]=dp[i-1]\n",
    "                    ones[i]=ones[i-1]+1\n",
    "                else:\n",
    "                    ones[i]=ones[i-1]\n",
    "                    dp[i]=min(ones[i],dp[i-1]+1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp1=[0 for i in range(n)] #0\n",
    "        dp2=[0 for i in range(n)] #1\n",
    "\n",
    "        dp1[0]=0 if s[0]=='0' else 1\n",
    "        dp2[0]=0 if s[0]=='1' else 1\n",
    "\n",
    "        i=1\n",
    "        while i<n:\n",
    "            if s[i]=='0':\n",
    "                dp1[i]=dp1[i-1]\n",
    "                dp2[i]=min(dp1[i-1], dp2[i-1])+1\n",
    "            else:\n",
    "                dp1[i]=dp1[i-1]+1\n",
    "                dp2[i]=min(dp1[i-1], dp2[i-1])\n",
    "            i+=1\n",
    "\n",
    "        return min(dp1[-1], dp2[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        res = l\n",
    "        num0 = [0] * l\n",
    "        num1 = [0] * l\n",
    "        for i in range(1, l):\n",
    "            num1[i] = num1[i - 1] if s[i - 1] == '0' else num1[i - 1] + 1\n",
    "            num0[l - i - 1] = num0[l - i] if s[l - i] == '1' else num0[l - i] + 1\n",
    "        for i in range(l):\n",
    "            res = min(num0[i] + num1[i], res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        res = l\n",
    "        num0 = [0] * l\n",
    "        num1 = [0] * l\n",
    "        for i in range(1, l):\n",
    "            num1[i] = num1[i - 1] if s[i - 1] == '0' else num1[i - 1] + 1\n",
    "            num0[l - i - 1] = num0[l - i] if s[l - i] == '1' else num0[l - i] + 1\n",
    "        for i in range(l):\n",
    "            res = min(num0[i] + num1[i], res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp_0 = list()\n",
    "        dp_1 = list()\n",
    "        dp_0.append(0 if s[0]=='0' else 1)\n",
    "        dp_1.append(0 if s[0]=='1' else 1)\n",
    "        for i in range(1,len(s)):\n",
    "            dp_0.append(dp_0[-1]+(s[i]=='1'))\n",
    "            dp_1.append(min(dp_0[-2], dp_1[-1])+ (s[i]=='0'))\n",
    "        return min(dp_1[-1], dp_0[-1])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        presum1 = [0] * (n+1)\n",
    "        postsum0 = [0] * (n+1)\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            presum1[i] = presum1[i-1] + int(s[i-1])\n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            postsum0[i] = postsum0[i+1] + int(s[i]=='0')\n",
    "\n",
    "        dp = [0] * (n+1)\n",
    "        for i in range(n+1):\n",
    "            dp[i] = presum1[i] + postsum0[i]\n",
    "        \n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        ans=[[0]*2 for _ in range(n)]\n",
    "        for i in range(n):  #第i位是0/1情况下最小转换次数\n",
    "            if s[i]=='0':\n",
    "                ans[i][0]=ans[i-1][0]\n",
    "                ans[i][1]=min(ans[i-1][0],ans[i-1][1])+1 #改成1\n",
    "            else:\n",
    "                ans[i][0]=ans[i-1][0]+1    #改成0\n",
    "                ans[i][1]=min(ans[i-1][0],ans[i-1][1])\n",
    "        return min(ans[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        right = [0]*len(s)\n",
    "        summ = 0\n",
    "        for j in range(len(s)-1, -1, -1):\n",
    "            if s[j] == \"0\":\n",
    "                summ += 1\n",
    "            right[j] = summ\n",
    "        \n",
    "        res = len(s)\n",
    "\n",
    "        print(right)\n",
    "        cache = 0\n",
    "        for j in range(len(s)):\n",
    "            if s[j] == \"1\":\n",
    "                res = min(res, cache+right[j])\n",
    "                cache += 1\n",
    "        res = min(res, cache)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        self.len = len(s)\n",
    "        s = list(map(int, list(s)))\n",
    "        dp_0 = [0 for _ in range(self.len)]\n",
    "        dp_1 = [0 for _ in range(self.len)]\n",
    "        if s[0]==1:\n",
    "            dp_0[0]=1\n",
    "        for i in range(1,self.len):\n",
    "            if s[i]==0:\n",
    "                dp_0[i] = dp_0[i-1]\n",
    "                dp_1[i] = min(dp_0[i], dp_1[i-1]+1)\n",
    "            else:\n",
    "                dp_0[i] = dp_0[i-1]+1\n",
    "                dp_1[i] = min(dp_0[i], dp_1[i-1])\n",
    "        return min(dp_0[-1], dp_1[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        # 表示第一行当前字符串翻转后结果是0\n",
    "        # 表示第二行当前字符串翻转后结果是1\n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "        num0 = int(s[0])\n",
    "        dp[0][1-num0] = 1\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if s[i] == '0':\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                #dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1\n",
    "                dp[i][1] =  dp[i-1][1] + 1\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0] + 1\n",
    "                dp[i][1] = min(dp[i-1][1], dp[i-1][0])\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp0, dp1 = [0] * n, [0] * n\n",
    "        dp0[0] = 0 if s[0] == '0' else 1\n",
    "        dp1[0] = 1 if s[0] == '0' else 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            c = s[i]\n",
    "            dp0[i] = dp0[i - 1] + (1 if c == '1' else 0)\n",
    "            dp1[i] = min(dp0[i - 1], dp1[i - 1]) + (1 if c == '0' else 0)\n",
    "        \n",
    "        # print (dp0, dp1)\n",
    "        return min(dp0[n - 1], dp1[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left, right = [0] * n, [0] * n\n",
    "        if s[0] == '1':\n",
    "            left[0] = 1\n",
    "        if s[-1] == '0':\n",
    "            right[-1] = 1\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if s[i] == '1':\n",
    "                left[i] = left[i - 1] + 1\n",
    "            else:\n",
    "                left[i] = left[i - 1]\n",
    "        \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if s[i] == '0':\n",
    "                right[i] = right[i + 1] + 1\n",
    "            else:\n",
    "                right[i] = right[i + 1]\n",
    "        \n",
    "        print(left, right)\n",
    "        \n",
    "        return min(left[i] + right[i] - 1 for i in range(n))\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[inf]*n for _ in range(2)]\n",
    "        for i in range(2): dp[i][0] = int(s[0])^i\n",
    "\n",
    "        for j in range(1, n):\n",
    "            for i in range(2):\n",
    "                cur = int(s[j])^i\n",
    "                if i==0: \n",
    "                    dp[i][j] = cur+dp[0][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = cur+min(dp[0][j-1], dp[1][j-1])\n",
    "        \n",
    "        return min(dp[0][n-1], dp[1][n-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[inf]*n for _ in range(2)]\n",
    "        for i in range(2): dp[i][0] = int(s[0])^i\n",
    "\n",
    "        for j in range(1, n):\n",
    "            for i in range(2):\n",
    "                cur = int(s[j])^i\n",
    "                if i==0: \n",
    "                    dp[i][j] = cur+dp[0][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = cur+min(dp[0][j-1], dp[1][j-1])\n",
    "        \n",
    "        return min(dp[0][n-1], dp[1][n-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp=[[0]*2 for _ in range(len(s))]\n",
    "        if s[0]=='0':\n",
    "            dp[0][1]=1\n",
    "        else:\n",
    "            dp[0][0]=1\n",
    "        \n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]=='0':\n",
    "                dp[i][0]=dp[i-1][0]\n",
    "                dp[i][1]=min(dp[i-1][0],dp[i-1][1])+1\n",
    "            else:\n",
    "                dp[i][0]=dp[i-1][0]+1\n",
    "                dp[i][1]=min(dp[i-1][0],dp[i-1][1])\n",
    "        \n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[None for j in range(n)] for i in range(2)]\n",
    "        dp[0][0] = 1 if s[0] == \"1\" else 0\n",
    "        dp[1][0] = 1 if s[0] == \"0\" else 0\n",
    "        for i in range(1, n):\n",
    "            cur = int(s[i])\n",
    "            dp[0][i] = dp[0][i-1] + cur % 2\n",
    "            dp[1][i] = min(dp[0][i-1] + (cur+1) % 2, dp[1][i-1] + (cur+1) % 2)\n",
    "        return min(dp[0][-1], dp[1][-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        tail_0 = [0] * len(s)\n",
    "        head_1 = [0] * len(s)\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            cur_1 = (1 if s[i] == \"1\" else 0)\n",
    "            if i == 0:\n",
    "                head_1[i] = cur_1\n",
    "            else:\n",
    "                head_1[i] = head_1[i-1] + cur_1\n",
    "        for i in list(range(n))[::-1]:\n",
    "            cur_0 = (1 if s[i] == \"0\" else 0)\n",
    "            if i == n - 1:\n",
    "                tail_0[i] = cur_0\n",
    "            else:\n",
    "                tail_0[i] = tail_0[i+1] + cur_0\n",
    "\n",
    "        print(tail_0)\n",
    "        print(head_1)\n",
    "        result = len(s)\n",
    "        result = min(result, tail_0[0])\n",
    "        result = min(result, head_1[-1])\n",
    "        for i in range(n - 1):\n",
    "            result = min(result, tail_0[i + 1] + head_1[i])\n",
    "        return result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp1=[0 for i in range(n)] #0\n",
    "        dp2=[0 for i in range(n)] #1\n",
    "\n",
    "        dp1[0]=0 if s[0]=='0' else 1\n",
    "        dp2[0]=0 if s[0]=='1' else 1\n",
    "\n",
    "        i=1\n",
    "        while i<n:\n",
    "            dp1[i]=dp1[i-1] + (0 if s[i] =='0' else 1)\n",
    "            dp2[i]=min(dp1[i-1], dp2[i-1]) + (1 if s[i] =='0' else 0)\n",
    "            i+=1\n",
    "\n",
    "        return min(dp1[-1], dp2[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "\n",
    "        s = [eval(i) for i in s]\n",
    "        dp = [[0,0] for i in range(len(s))]\n",
    "        dp[0][0] = 0 if s[0]==0 else 1\n",
    "        dp[0][1] = 0 if s[0]==1 else 1\n",
    "        res = [min(dp[0][0],dp[0][1] )]\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if i==0:\n",
    "                continue\n",
    "            v = s[i]\n",
    "            if v==0:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = min(dp[i-1][0]+1, dp[i-1][1]+1)\n",
    "            elif v==1:\n",
    "                dp[i][0] = dp[i-1][0]+1\n",
    "                dp[i][1] = min(dp[i-1][0], dp[i-1][1])\n",
    "            res.append(min(dp[i][0], dp[i][1]))\n",
    "\n",
    "        return res[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # self.cnt = 0\n",
    "        # self.all = 0\n",
    "        # def recurse(track, idx, s):\n",
    "        #     self.all +=1\n",
    "        #     k = track\n",
    "        #     if k in self.memo:\n",
    "        #         self.cnt +=1\n",
    "        #         return self.memo[k]\n",
    "        #     if idx ==len(s):\n",
    "        #         return 0\n",
    "        #     if s[idx]=='1':\n",
    "        #         if track=='' or (len(track)>0 and track[-1]=='0'):\n",
    "        #             # 反转 \n",
    "        #             r1 = 1+ recurse(track+'0', idx+1, s)\n",
    "        #             # 不反转 \n",
    "        #             r2 = recurse(track+'1', idx+1, s)\n",
    "        #             self.memo[k] = min(r1, r2)\n",
    "        #             return min(r1, r2)\n",
    "        #         elif len(track)>0 and track[-1]=='1':\n",
    "        #             r = recurse(track+'1', idx+1, s)\n",
    "        #             self.memo[k] = r \n",
    "        #             return r \n",
    "                \n",
    "        #     else:\n",
    "        #         if track =='':\n",
    "        #             # 反转\n",
    "        #             r1 = 1+ recurse(track+'1', idx+1, s)\n",
    "        #             # 不反转\n",
    "        #             r2 = recurse(track+'0', idx+1, s)\n",
    "        #             self.memo[k] = min(r1, r2)\n",
    "        #             return min(r1, r2)\n",
    "        #         elif track[-1]=='0':\n",
    "        #             r = recurse(track+'0', idx+1, s)\n",
    "        #             self.memo[k] = r\n",
    "        #             return r \n",
    "        #         elif track[-1]=='1':\n",
    "        #             r = 1+recurse(track+'1', idx+1, s)\n",
    "        #             self.memo[k] = r \n",
    "        #             return r\n",
    "        # self.memo = {}\n",
    "        # res = recurse('', 0, s)\n",
    "        # print(self.cnt, self.all)\n",
    "        # return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"以当前字符结尾的最小翻转次数，将当前字符反转为之前最下反转次数相同的字符即可\"\"\"\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp0 = [float('inf') for i in range(len(s))]\n",
    "        dp1 = [float('inf') for i in range(len(s))]\n",
    "        if s[0] == '0':\n",
    "            dp1[0] = 1\n",
    "            dp0[0] = 0\n",
    "        else:\n",
    "            dp0[0] = 1\n",
    "            dp1[0] = 0\n",
    "\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] == '0':\n",
    "                dp0[i] = dp0[i-1]  #以0结尾不需要反转\n",
    "                dp1[i] = min(dp1[i-1]+1,dp0[i-1]+1)   #以1结尾需要反转\n",
    "            else:\n",
    "                dp0[i] = dp0[i-1]+1 #以0结尾需要反转\n",
    "                dp1[i] = min(dp1[i-1],dp0[i-1])    #以1结尾需要反转\n",
    "        return min(dp1[-1],dp0[-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp0, dp1 = [0] * n, [0] * n\n",
    "        dp0[0] = 0 if s[0] == '0' else 1\n",
    "        dp1[0] = 1 if s[0] == '0' else 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            c = s[i]\n",
    "            dp0[i] = dp0[i - 1] + (1 if c == '1' else 0)\n",
    "            dp1[i] = min(dp0[i - 1], dp1[i - 1]) + (1 if c == '0' else 0)\n",
    "        \n",
    "        print (dp0, dp1)\n",
    "        return min(dp0[n - 1], dp1[n - 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        DP_0 = [0] * len(s)\n",
    "        DP_1 = [0] * len(s)\n",
    "        DP_0[0] = 0 if s[0] == \"0\" else 1\n",
    "        DP_1[0] = 0 if s[0] == \"1\" else 1\n",
    "        for i in range(1, len(s)):\n",
    "            DP_0[i] = DP_0[i-1] + 0 if s[i] == \"0\" else DP_0[i-1] + 1\n",
    "            DP_1[i] = min(DP_0[i-1], DP_1[i-1]) + 0 if s[i] == \"1\" else min(DP_0[i-1], DP_1[i-1]) + 1\n",
    "        print(DP_0)\n",
    "        print(DP_1)\n",
    "        \n",
    "        return min(DP_0[-1], DP_1[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        length=len(s)\n",
    "        dp=[[0,0] for _ in range(length+1)]\n",
    "\n",
    "        for i in range(1,length+1):\n",
    "            if s[i-1]=='0':\n",
    "                dp[i][0]=dp[i-1][0]\n",
    "                dp[i][1]=1+min(dp[i-1][0],dp[i-1][1])\n",
    "            else:\n",
    "                dp[i][0]=1+dp[i-1][0]\n",
    "                dp[i][1]=min(dp[i-1][0],dp[i-1][1])\n",
    "        \n",
    "        # print(dp)\n",
    "\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        # dp[i][0] = dp[i-1][0] + (0 ^ int(c)), dp[i][1] = min(dp[i-1][0] + (1 ^ int(c)),dp[i-1][1] + (1 ^ int(c))) 1 <= i < n\n",
    "        # dp[0][0] = 0 ^ int(c), dp[0][1] = 1 ^ int(c)\n",
    "        # i += 1\n",
    "        # dp[i-1]->dp[i]\n",
    "        n = len(s)\n",
    "        dp = [[0 for i in range(2)] for i in range(n)]\n",
    "        dp[0][0], dp[0][1] = 0 ^ int(s[0]), 1 ^ int(s[0])\n",
    "        first, second = 0 ^ int(s[0]), 1 ^ int(s[0])\n",
    "        for i in range(1,n):\n",
    "            first, second = first + (0 ^ int(s[i])), min(first + (1 ^ int(s[i])),second + (1 ^ int(s[i]))) \n",
    "        return min(first,second)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp0 = [0]*n\n",
    "        dp1=[0]*n\n",
    "        if s[0] == '0':\n",
    "            dp1[0] = 1\n",
    "        else:\n",
    "            dp0[0] = 1\n",
    "        for i in range(1,n):\n",
    "            dp0[i] = dp0[i-1]+(0 if s[i] == '0' else 1)\n",
    "            dp1[i] = min(dp0[i-1],dp1[i-1])+(0 if s[i] == '1' else 1) \n",
    "        return min(dp0[-1],dp1[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:  \n",
    "        n=len(s)\n",
    "        dp=[ [0] * n for i in range(2)]\n",
    "        dp[0][0]=(0 if s[0]=='0' else 1)\n",
    "        dp[1][0]=(1 if s[0]=='0' else 0)\n",
    "        for i in range(1,n):\n",
    "            dp[0][i]=dp[0][i-1] + (0 if s[i]=='0' else 1)\n",
    "            dp[1][i]=min(dp[1][i-1],dp[0][i-1])+(1 if s[i]=='0' else 0)\n",
    "        return min(dp[0][n-1],dp[1][n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        lens = len(s)\n",
    "        dp = [[0,0] for _ in range(lens)]\n",
    "        dp[0][0] = 0 if s[0] == '0' else 1\n",
    "        dp[0][1] = 0 if s[0] == '1' else 1\n",
    "        for i in range(1, lens):\n",
    "            dp[i][0] = dp[i-1][0]+(0 if s[i] == '0' else 1)\n",
    "            dp[i][1] = min(dp[i-1][1], dp[i-1][0])+(0 if s[i] == '1' else 1)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [[0 for i in range(2)] for j in range(len(s))]\n",
    "\n",
    "        dp[0][0] = 1 if s[0]=='1' else 0\n",
    "        dp[0][1] = 1 if s[0]=='0' else 0\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i]=='0':\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = min(dp[i-1][0], dp[i-1][1])+1\n",
    "            elif s[i]=='1':\n",
    "                dp[i][0] = dp[i-1][0]+1\n",
    "                dp[i][1] = min(dp[i-1][0], dp[i-1][1])\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        prefix,suffix=[0 for i in range(n+1)],[0 for i in range(n+1)]\n",
    "        for i in range(n):\n",
    "            prefix[i]=prefix[i-1]+int(s[i])\n",
    "        for i in range(n-1,-1,-1):\n",
    "            suffix[i]=suffix[i+1]+int(s[i])\n",
    "        min_flip=n-suffix[0]\n",
    "        for i in range(n):\n",
    "            min_flip=min(min_flip,prefix[i]+(n-i-1-suffix[i+1]))\n",
    "        return min_flip"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        left_1s = [0 for _ in range(n)]\n",
    "        right_0s = [0 for _ in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            left_1s[i] = left_1s[i - 1] + (1 if s[i - 1] == '1' else 0)\n",
    "        for j in range(n - 2, -1, -1):\n",
    "            right_0s[j] = right_0s[j + 1] + (1 if s[j + 1] == '0' else 0)\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            ans = min(ans, left_1s[i] + right_0s[i])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        prefix = [0] * (n+1)  # 前缀和数组，prefix[i] 表示 s 中前 i 个字符 '1' 的数量\n",
    "        suffix = [0] * (n+1)  # 后缀和数组，suffix[i] 表示 s 中后 i 个字符 '0' 的数量\n",
    "        for i in range(1, n+1):\n",
    "            prefix[i] = prefix[i-1] + (s[i-1] == '1')\n",
    "        for i in range(n-1, -1, -1):\n",
    "            suffix[i] = suffix[i+1] + (s[i] == '0')\n",
    "        return min(prefix[i] + suffix[i] for i in range(n+1)) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        left=[0]\n",
    "        for i in range(1,len(s)):\n",
    "            left.append(left[-1]+int(s[i-1]))\n",
    "        right=[0]\n",
    "        for i in range(len(s)-2,-1,-1):\n",
    "            right.insert(0,right[0]+1-int(s[i+1]))\n",
    "        ans=math.inf\n",
    "        for i in range(len(s)):\n",
    "            ans=min(ans,left[i]+right[i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [[0,1]] if s[0] == '0' else [[1,0]]\n",
    "        \n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == '1':\n",
    "                dp.append([dp[-1][0] + 1, min(dp[-1][1], dp[-1][0])])\n",
    "            else:\n",
    "                dp.append([dp[-1][0], dp[-1][1] + 1])\n",
    "        \n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0, 0] for _ in range(n)]\n",
    "        if s[0] == '0':\n",
    "            dp[0][1] = 1\n",
    "        else:\n",
    "            dp[0][0] = 1\n",
    "        for i in range(1, n):\n",
    "            if s[i] == '0':\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = min(dp[i-1]) + 1\n",
    "            else:\n",
    "                dp[i][0] = 1 + dp[i-1][0]\n",
    "                dp[i][1] = min(dp[i-1])\n",
    "\n",
    "        # print(dp)\n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0 for _ in range(2)] for _ in range(n)]\n",
    "        dp[0][0] = (0 if s[0] == \"0\" else 1)\n",
    "        dp[0][1] = (0 if s[0] == \"1\" else 1)\n",
    "        for i in range(1, n):\n",
    "            if s[i] == \"1\":\n",
    "                n, m = 1, 0\n",
    "            else:\n",
    "                n, m = 0, 1\n",
    "            dp[i][0] = dp[i - 1][0] + n\n",
    "            dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + m\n",
    "        \n",
    "        return min(dp[-1][0], dp[-1][1])\n",
    "\n",
    "\n",
    "# dp = [[0] * 2 for i in range(len(s))]\n",
    "#         dp[0][0] = 0 if s[0] == \"0\" else 1\n",
    "#         dp[0][1] = 0 if s[0] == \"1\" else 1\n",
    "\n",
    "#         for i in range(1, len(s)):\n",
    "#             temp_zero = 0 if s[i] == \"0\" else 1\n",
    "#             temp_one = 1 if s[i] == \"0\" else 0\n",
    "#             dp[i][0] = dp[i - 1][0] + temp_zero\n",
    "#             dp[i][1] = min(dp[i - 1][0] + temp_one, dp[i - 1][1] + temp_one)\n",
    "        \n",
    "#         return min(dp[-1][0], dp[-1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        \n",
    "        # dp[i][0] = dp[i-1][0] + I(s[i] == 1)\n",
    "        # dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + I(s[i] == 0)\n",
    "\n",
    "        dp = [[0 for _ in range(2)] for _ in range(len(s))]\n",
    "\n",
    "        dp[0][0] = 0 if s[0] == \"0\" else 1\n",
    "        dp[0][1] = 0 if s[0] == \"1\" else 1\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "            dp[i][0] = dp[i-1][0] + (1 if s[i] == \"1\" else 0)\n",
    "            dp[i][1] =  min(dp[i-1][0], dp[i-1][1]) + (1 if s[i] == \"0\" else 0)\n",
    "\n",
    "        return min(dp[-1][0], dp[-1][1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp=[[0]*2 for _ in range(len(s))]   #dp[i][1] 表示第i个数字变为1且保证前i个数字都是递增的最小反转次数\n",
    "        for i in range(len(s)):\n",
    "            for j in range(2):\n",
    "                if i == 0:\n",
    "                    dp[i][j] = int(s[i])^j\n",
    "                else:\n",
    "                    if j == 0:\n",
    "                        # print('--------')\n",
    "                        # print('i=',i)\n",
    "                        # print(s[i])\n",
    "                        # print(int(s[i])^j)\n",
    "                        # print(dp[i-1][0])\n",
    "                        # print(dp[i][j])\n",
    "                        dp[i][j] = (int(s[i])^j)+dp[i-1][0]\n",
    "                        # print(dp[i][j])\n",
    "                    else:\n",
    "                        dp[i][j] = (int(s[i])^j)+min(dp[i-1])\n",
    "        print(dp)\n",
    "        return min(dp[len(s)-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        \"\"\"dp i  为 左边为1 的个数 + 右边为 0 的个数\n",
    "        \"\"\"\n",
    "        length = len(s)\n",
    "        dp_one = [0] * length\n",
    "        dp_zero = [0] * length\n",
    "        for i in range(0,length):\n",
    "            if i > 0:\n",
    "                dp_one[i] = dp_one[i-1] + int(s[i])\n",
    "            else:\n",
    "                dp_one[i] = int(s[i])\n",
    "        print(dp_one)\n",
    "        for i in range(0,length):\n",
    "            if i > 0:\n",
    "                dp_zero[i] = length - 1 - i - (dp_one[-1] - dp_one[i]) + dp_one[i]\n",
    "            else:\n",
    "                dp_zero[i] = length - 1 - i - (dp_one[-1] - dp_one[i])\n",
    "        print(dp_zero)\n",
    "        return min(dp_zero)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*2 for _ in range(n)]\n",
    "        dp[0][0] = int(s[0])\n",
    "        dp[0][1] = 1 - int(s[0])\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = dp[i-1][0] + int(s[i])\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1 - int(s[i])\n",
    "        print(dp)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp=[]\n",
    "        for i in range(len(s)+1):\n",
    "            a=[]\n",
    "            for j in range(2):\n",
    "                a.append(0)\n",
    "            dp.append(a)\n",
    "        for i in range(len(s)):\n",
    "            #我想把当前的数作为结尾\n",
    "            if(s[i]=='0'):\n",
    "                #如果是0\n",
    "                dp[i+1][0]=dp[i][0]\n",
    "                #想用0做结尾，现在刚好是0，当前又不用变，而且前面一定是0，所以把前面的次数挪过来\n",
    "                dp[i+1][1]=min(dp[i][0],dp[i][1])+1\n",
    "                #想用1做结尾，现在是0，需要变，要加1，而且前面是0是1都可以，所以把前面的少的次数挪过来，然后加1\n",
    "            else:\n",
    "                #如果是1\n",
    "                dp[i+1][0]=dp[i][0]+1\n",
    "                #想用0做结尾，需要变，要加1，而且前面一定是0，所以把前面的次数挪过来+1\n",
    "                dp[i+1][1]=min(dp[i][0],dp[i][1])\n",
    "                #想用1做结尾，现在是1，不用变，而且前面是0是1都可以，所以把前面的少的次数挪过来\n",
    "        print(dp)\n",
    "        return min(dp[-1][0],dp[-1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [(int(s[0] != '0'), int(s[0] != '1'))]\n",
    "        for ix in range(1, len(s)):\n",
    "            tmp1 = dp[ix - 1][0] + int(s[ix] != '0')\n",
    "            tmp2 = min(dp[-1]) + int(s[ix] != '1')\n",
    "            dp.append((tmp1, tmp2))\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [[0, 0] for i in s]\n",
    "        filp = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '0':\n",
    "                dp[i][0] = 0\n",
    "                dp[i][1] = 1\n",
    "            elif s[i] == '1':\n",
    "                dp[i][0] = 1\n",
    "                dp[i][1] = 0\n",
    "            \n",
    "            if i > 0:\n",
    "                dp[i][0] = dp[i-1][0] + dp[i][0]\n",
    "                dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + dp[i][1]\n",
    "        print(dp)\n",
    "        return min(dp[len(s)-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        l = [[0, 0]]\n",
    "        for v in map(int, s):\n",
    "            l.append([l[-1][0] + v, l[-1][1] + (v ^ 1)])\n",
    "        ans = inf\n",
    "        a = b = 0\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            v = int(s[i])\n",
    "            a, b = a + v, b + (v ^ 1)  # 右侧变成0，右侧变成1\n",
    "            ans = min(ans, l[i][0] + a, l[i][0] + b, l[i][1] + b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # 为0结尾需要的反转次数， 为1结尾需要的反转次数\n",
    "        dp = [[0,0] for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == \"0\":\n",
    "                dp[i][0] = 0 if i == 0 else dp[i-1][0]\n",
    "                dp[i][1] = 1 if i == 0 else min(dp[i-1][0], dp[i-1][1]) + 1\n",
    "            else:\n",
    "                dp[i][0] = 1 if i == 0 else dp[i-1][0] + 1\n",
    "                dp[i][1] = 0 if i == 0 else min(dp[i-1][0], dp[i-1][1])\n",
    "                \n",
    "        return min(dp[n-1], default=0)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 0->1 dp[i][1] = min(dp[i-1][1]+1, dp[i-1][0]+1) dp[i][0] = dp[i-1][0]\n",
    "# 1->0 dp[i][0] = dp[i-1][0]+1\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        m = len(s)\n",
    "        dp = [[0]*2 for _ in range(m)]\n",
    "        if s[0] == '0':\n",
    "            dp[0][0], dp[0][1] = 0, 1\n",
    "        else:\n",
    "            dp[0][1], dp[0][0] = 0, 1\n",
    "        for i in range(1, m):\n",
    "            if s[i] == '0':\n",
    "                dp[i][1] = min(dp[i-1][1]+1, dp[i-1][0]+1)\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0]+1\n",
    "                dp[i][1] = min(dp[i-1][1], dp[i-1][0])\n",
    "        return min(dp[m-1][0], dp[m-1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [[0] * 2 for _ in range(len(s) +1)]\n",
    "        for i in range(1, len(s) +1):\n",
    "            # for j in range(2):\n",
    "                if s[i-1] == '1':\n",
    "                    dp[i][0] = dp[i-1][0] + 1\n",
    "                    dp[i][1] = min(dp[i-1][0], dp[i-1][1])\n",
    "                elif s[i-1] == '0':\n",
    "                    dp[i][0] = dp[i-1][0]\n",
    "                    dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [[0, 0] for i in s]\n",
    "        if s[0] == '1':dp[0][0] = 1 \n",
    "        else:dp[0][1] = 1\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == '1':\n",
    "                dp[i][0], dp[i][1] =  dp[i-1][0]+1, min(dp[i-1][0], dp[i-1][1])\n",
    "            else:\n",
    "                dp[i][0], dp[i][1] = dp[i-1][0], min(dp[i-1][0], dp[i-1][1]) + 1\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [[0, 0] for i in s]\n",
    "        if s[0] == '1':dp[0][0] = 1 \n",
    "        else:dp[0][1] = 1\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == '1':\n",
    "                dp[i][0], dp[i][1] =  dp[i-1][0]+1, min(dp[i-1][0], dp[i-1][1])\n",
    "            else:\n",
    "                dp[i][0], dp[i][1] = dp[i-1][0], min(dp[i-1][0], dp[i-1][1]) + 1\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        num=len(s)\n",
    "        dp=[['inf','inf'] for _ in range(num)]\n",
    "        dp[0][0]=int(s[0])\n",
    "        dp[0][1]=int(s[0]=='0')\n",
    "        for i in range(1,num):\n",
    "            dp[i][0]=dp[i-1][0]+int(s[i])\n",
    "            dp[i][1]=min(dp[i-1][0],dp[i-1][1])+int(s[i]=='0')\n",
    "        return min(dp[num-1][0],dp[num-1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * 2 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = dp[i-1][0] + (1 if s[i] == \"1\" else 0)\n",
    "            dp[i][1] = min(dp[i-1][0],dp[i-1][1]) + (1 if s[i] == \"0\" else 0)\n",
    "        return min(dp[-1][0],dp[-1][1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minFlipsMonoIncr(self, s: str) -> int:\n",
    "        dp = [[0,0] for i in range(len(s))]\n",
    "        if s[0]=='0': dp[0] = [0,1]\n",
    "        if s[0]=='1': dp[0] = [1,0]\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]=='0':\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "                dp[i][1] = min(dp[i-1])+1\n",
    "            elif s[i]=='1':\n",
    "                dp[i][0] = dp[i-1][0]+1\n",
    "                dp[i][1] = min(dp[i-1])\n",
    "        return min(dp[-1])\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
